offset = [(1, 2), (1, -2), (2, 1), (2, -1)]

a = []
count = 0

def main():
    global a
    a.append((0, 0))    #第0位不用
    search(a[:], (0, 0))

def output(a):
    global count
    count += 1
    print(count, ': ')
    r = []
    for i in range(1, len(a)):
        r.append((a[i][0], a[i][1]))
        r.append('-->')
    r.append((8, 4))
    print(r)

def search(a, next):
    # a.append(next)
    if len(a) > 9:
        return
    for j in range(4):
        nx = a[-1][0] + offset[j][0]
        ny = a[-1][1] + offset[j][1]
        if nx >= 0 and nx <= 8 and ny >= 0 and ny <= 4:
            if nx == 8 and ny == 4:
                output(a) 
                break
            else:
                search(a[:], (nx, ny))

main()
